#include <stdio.h>  
#include <stdlib.h>  
  
#define N 8  
  
int board[N][N];  
  
int is_valid(int row, int col) {  
    int i, j;  
    for (i = 0; i < row; i++) {  
        if (board[i][col] == 1) {  
            return 0;  
        }  
    }  
    for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {  
        if (board[i][j] == 1) {  
            return 0;  
        }  
    }  
    for (i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {  
        if (board[i][j] == 1) {  
            return 0;  
        }  
    }  
    return 1;  
}  
  
void place_queen(int row) {  
    int col;  
    for (col = 0; col < N; col++) {  
        if (is_valid(row, col)) {  
            board[row][col] = 1;  
            if (row == N - 1) {  
                printf("Solution found!\n");  
                for (int i = 0; i < N; i++) {  
                    for (int j = 0; j < N; j++) {  
                        printf("%d ", board[i][j]);  
                    }  
                    printf("\n");  
                }  
                return;  
            } else {  
                place_queen(row + 1);  
            }  
        }  
    }  
}  
  
int main() {  
    int i, j;  
    for (i = 0; i < N; i++) {  
        for (j = 0; j < N; j++) {  
            board[i][j] = 0;  
        }  
    }  
    place_queen(0);  
    return 0;  
}